Multipath routing is a router feature that allows a stream of packets going to a given destination to be split across multiple paths. Routers that do not support multipath routing only remember a single path to any given destination. As a result, if a link failure occurs along that path, network traffic to that destination may be stopped completely. Conventional routers that support multipath routing, on the other hand, remember multiple paths to any given destination. In the event of a failure that impacts one of the paths in a multipath arrangement, traffic can be shunted over to the surviving paths, thus reducing the impact of link failures. Multipath routing also allows the routers to balance traffic loads across multiple paths.
FIG. 1 illustrates a small network where multipath routing is supported. As shown, Router A has one connection to Router B and one connection to Router C. Router B and Router C each have a connection to Router D. To reach Router D, data packets from Router A can be routed via Router B and Router C. FIG. 2 illustrates the contents of Router A's routing table and shows the “cost” associated with each path. If the two paths have the same cost, Router A is indifferent to either path and may split traffic equally between both paths. If the path via Router B and the path via Router C have unequal bandwidths or “costs,” Router A may direct more traffic to the one connection with a lower cost than the one with a higher cost.
Multipath load balancing can be performed on a “per packet” basis or a “per destination” basis. Balancing multipath traffic on a per packet basis means that packets bound for the same destination are distributed to different interfaces. For example, with reference to FIGS. 1 and 2, Router A can route half of the data packets bound for destination IP address 192.68.253.5 via Router B and half of the data packets bound for the same destination IP address via Router C. Balancing traffic on a per-packet basis is typically not too resource intensive. However, some data may be received late, or out of sequence, which can cause application problems.
Multipath load balancing on a per destination basis means that packets bound for the same destination will be forwarded via the same path. For example, with reference to FIG. 1, Router A can route all data packets bound for destination IP address 192.68.253.5 via Router B while routing all data packets bound for destination IP address 192.68.253.2 via Router C. Balancing traffic on a per-destination basis alleviates some potential problems caused by per-packet load balancing. One drawback of balancing traffic on a per-destination basis, however, is that it is more resource intensive than load balancing on a per-packet basis. A significant amount of memory is used in conventional routers to cache route information such that packets bound for the same destination can be routed via the same path. Another drawback is that it is difficult to control the percentage of traffic routed through a particular path.
In view of the foregoing, what is needed is a router that can handle multipath routing and load balancing in a resource-efficient manner. What is also needed is a method of handling multipath load balancing in a resource-efficient manner.